//输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 
//
// 
//
// 示例 1: 
//
// 输入: [10,2]
//输出: "102" 
//
// 示例 2: 
//
// 输入: [3,30,34,5,9]
//输出: "3033459" 
//
// 
//
// 提示: 
//
// 
// 0 < nums.length <= 100 
// 
//
// 说明: 
//
// 
// 输出结果可能非常大，所以你需要返回一个字符串而不是整数 
// 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 
// 
// Related Topics 排序 
// 👍 87 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.Arrays;

/**
 * Java：把数组排成最小的数
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P剑指_offer_45_BaShuZuPaiChengZuiXiaoDeShuLcof {
    public static void main(String[] args) {
        Solution solution = new P剑指_offer_45_BaShuZuPaiChengZuiXiaoDeShuLcof().new Solution();
        String s = solution.minNumber(MyUtil.createArray(5, 54, 52, 67, 68, 5, 52, 17, 93, 53));
        MyUtil.print(s);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minNumber(int[] nums) {
            StringBuilder sb = new StringBuilder();
            String[] strs = new String[nums.length];
            for (int i = 0; i < nums.length; i++) {
                strs[i] = String.valueOf(nums[i]);
            }
            Arrays.sort(strs);
            MyUtil.print(Arrays.toString(strs));
            int i = 0, j = 1;
            while (i < strs.length && j < strs.length) {
                if ("-1".equals(strs[i])) {
                    i++;
                    continue;
                }
                if ("-1".equals(strs[j])) {
                    j++;
                    continue;
                }
                if (i == j) {
                    j++;
                    continue;
                }
                String vi = strs[i];
                String vj = strs[j];
                if (vi.equals(vj)) {
                    j++;
                    continue;
                }
                if ((vi + vj).compareTo(vj + vi) < 0) {
                    sb.append(vi);
                    strs[i++] = "-1";
                } else {
                    sb.append(vj);
                    strs[j++] = "-1";
                }
            }

            for (String str : strs) {
                if (!"-1".equals(str)) {
                    sb.append(str);
                }
            }
            return sb.toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}